package linkedlist;

import java.util.List;

/**
 * @author <a href="zhaoyingling12@163.com">Zhao Simon</a>
 * @description: https://leetcode.cn/problems/reverse-linked-list-ii/ 92.反转链表2
 * @date 2023/03/02
 **/
public class ReverseLinkedListII {


    class Solution {
        public ListNode reverseBetween(ListNode head, int left, int right) {
            if (head == null || head.next == null) {
                return head;
            }

            // 无意义的node
            ListNode dummyNode = new ListNode(-1);
            dummyNode.next = head;

            // 核心是找到 leftNode, leftLastNode, rightNode, rightNextNode
            // order leftLastNode -> leftNode -> ... -> rightNode -> rightNextNode
            ListNode cur = dummyNode, leftLastNode = null, leftNode = null, rightNode = null, rightNextNode = null;

            int cnt = 0;

            while (cnt < right) {
                if (cnt + 1 == left) {
                    leftLastNode = cur;
                }
                if (cnt == left) {
                    leftNode = cur;
                }
                if (cnt == right) {
                    rightNode = cur;
                    rightNextNode = rightNode.next;
                }
                cur = cur.next;
                cnt++;
            }

            reverse(leftNode, rightNode);

            leftNode.next = rightNextNode;
            if (left != 1) {
                leftLastNode.next = rightNode;
            }

            return left == 1 ? rightNode : head;
        }

        private void reverse(ListNode leftNode, ListNode rightNode) {

            if (leftNode == rightNode) {
                return;
            }
            ListNode cur = leftNode, lastNode = null;

            while (cur != rightNode) {
                ListNode next = cur.next;
                cur.next = lastNode;
                lastNode = cur;
                cur = next;
            }
            cur.next = lastNode;
        }

    }
}
